package com.jeff.learn.sort;

/**
 * 使用循环实现插入排序
 *
 * @author yaojianfeng
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 8, 6, 3, 1, 7, 4};
        insertSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }

    }

    /**
     * 插入排序 时间复杂度O(n^2)
     *
     * @param arr 待排序数组
     */
    public static void insertSort(int[] arr) {
        // 外层循环控制待排序数组的长度
        for (int i = 1; i < arr.length; i++) {
            // 内层循环控制待排序数组的元素
            // 内层循环从待排序数组的第i个元素开始，与前面已排序的元素比较，如果比前面元素小，则交换位置
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    // 如果比前面元素小，则交换位置
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    // 如果比前面元素大，则不需要交换位置，直接退出内层循环
                    break;
                }
            }
        }
    }
}
